package com.demo39_组合总合;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution_剪枝 {
    public static void main(String[] args) {
        int[] ints = {2, 3, 6, 7};
        List<List<Integer>> lists = combinationSum(ints, 7);

        System.out.println(lists);

    }

    public static List<List<Integer>> combinationSum(int[] candidates, int target) {
        //1.给数组排序
        Arrays.sort(candidates);
        List<List<Integer>> arrayLists = new ArrayList<>();
        //2.特殊判断
        if (candidates[0] > target) {
            return arrayLists;
        }
        ArrayList<Integer> path = new ArrayList<>();
        dfs(candidates, target, 0, 0, arrayLists, path);
        return arrayLists;
    }

    private static void dfs(int[] candidates, int target, int startIndex, int sum, List<List<Integer>> arrayLists, ArrayList<Integer> path) {
        //1.边界条件
        if (target == sum) {
            ArrayList<Integer> copy = new ArrayList<>();
            for (Integer integer : path) {
                copy.add(integer);
            }
            arrayLists.add(copy);
            return;
        }

        /**
         * 把此处的判断放在for循环这里 ,作为剪枝操作:   直接在for循环这里掐掉
         */
        /*if (sum>target){
            return ;
        }*/
        //2.横向遍历: 这里必须要用这个 startIndex, 这样的话, 可以保证我们所挑选的组合不重复
        for (int i = startIndex; i < candidates.length && (sum + candidates[i] <= target); i++) {

            path.add(candidates[i]);
            sum += candidates[i];
            //3.递归 纵向遍历
            dfs(candidates, target, i, sum, arrayLists, path);
            //3.回溯
            path.remove(path.size() - 1);
            sum -= candidates[i];
        }
    }

    // 不用这个了,感觉还是费时间
    /*public static int sum(List<Integer> list){
        int sum=0;
        for (Integer integer : list) {
            sum+=integer;
        }
        return sum;
    }*/


}
